package com.duoduo.数组;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 下一个排列31
 * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
 * <p>
 * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
 * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
 * <p>
 * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
 * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
 * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 * <p>
 * 必须 原地 修改，只允许使用额外常数空间。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 * @author: chaidl  ！
 * @create: 2022-05-07 22:38
 */
public class 下一个排列31 {
	// 1,2,3,8,5,7,6,4
	// 1,2,3,8,6,4,5,7
	public void nextPermutation(int[] nums) {
		//从倒数第二个数字开始和后面比较
		int i = nums.length - 2;
		/*找到数组中的“小数”，退出循环就说明nums[i] < nums[i + 1]*/
		while (i >= 0 && nums[i] >= nums[i + 1]) {
			i--;
		}
		if (i >= 0) {
			int j = nums.length - 1;
			/*找到数组中的尽可能小的“大数，退出循环就说明nums[i] < nums[j]”*/
			while (j >= 0 && nums[i] >= nums[j]) {
				j--;
			}
			/*交换“小数”和“大数”的位置*/
			swap(nums, i, j);
		}
		/*将“大数”后面的所有数重置为升序*/
		reverse(nums, i + 1);
	}
	
	/**
	 * 双指针
	 *
	 * @param nums
	 */
	public void nextPermutation2(int[] nums) {
		for (int i = nums.length - 1; i >= 0; i--) {
			for (int j = nums.length - 1; j > i; j--) {
				//如果左边树小于右边的数
				if (nums[i] < nums[j]) {
					//交换他们的位置
					swap(nums, i, j);
					//	d对于i后面的数进行排序
					Arrays.sort(nums, i + 1, nums.length);
					return;
				}
			}
		}
		Arrays.sort(nums);
	}
	
	public void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
	
	public void reverse(int[] nums, int start) {
		int left = start, right = nums.length - 1;
		while (left < right) {
			swap(nums, left, right);
			left++;
			right--;
		}
	}
	
	public static void main(String[] args) {
		int[] nums1 = {5, 3, 1, 6, 2, 4};
		int[] nums2 = {1, 2, 3, 4, 5, 6};
		int[] nums4 = {3,2,1};
		int[] nums3 = {1,2,3,8,5,7,6,4};
		new 下一个排列31().nextPermutation(nums4);
		for (int i : nums3) {
			System.out.print(i);
		}
	}
}
